package com.xq.algorithm.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/15.
 */

public class BinaryTreeAlgorithm {

    /**
     * 二叉树的先序遍历思路:
     * 树的遍历，最常见的有先序遍历，中序遍历，后序遍历和层序遍历，它们用递归实现起来都非常的简单。而题目的要求是不能使用递归求解，于是只能考虑到用非递归的方法，这就要用到stack来辅助运算。由于先序遍历的顺序是"根-左-右", DLR 算法为：
     1. 把根节点push到栈中
     2. 循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在则push到栈中。再看其左子节点，若存在，则push到栈中。
     * @param root
     * @return
     */
    public static List<Integer> preOrderTraversal(TreeNode root){
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) return resList;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode p = stack.pop();
            //取出栈顶元素，保存值到List里面
            resList.add(p.val);
            //因为是栈辅助，根据栈的特点后进先出，所以先看右节点是否存在存在压入栈中，接着再看左节点，存在压入栈中
            if(p.right != null) stack.push(p.right);
            if(p.left != null) stack.push(p.left);
        }
        return resList;
    }

    /**
     * 二叉树的中序遍历
     * 从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。
     * 这样就保证了访问顺序为左-根-右
     * @param root
     * @return
     */
    public static List<Integer> inOrderTraversal(TreeNode root){
        ArrayList<Integer> resList = new ArrayList<>();
        if(root == null) return resList;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            //将左子树上的节点入栈
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }

            //如果已经到了树的最左边，则将栈中的节点出栈。
            cur = stack.pop();
            resList.add(cur.val);

            cur = cur.right;
        }
        return resList;
    }

    /**
     * 二叉树的后续遍历
     *  二叉树的后序遍历的非递归方法，跟前序，中序，层序一样都需要用到栈，后续的顺序是左-右-根，所以当一个节点值被取出来时，它的左右子节点要么不存在，要么已经被访问过了。
     * @param root
     * @return
     */
    public static List<Integer> postOrderTraversal(TreeNode root){
        ArrayList<Integer> resList = new ArrayList<>();
        if(root == null)return resList;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode head = root;
        while (!stack.empty()){
            TreeNode top = stack.pop();
            if((top.left == null && top.right == null) || top.left == head || top.right == head){
                resList.add(top.val);
                head = stack.pop();
            }else {
                if(top.right != null)stack.push(top.right);
                if(top.left != null)stack.push(top.left);
            }
        }
        return resList;

    }

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }
}
